11590 - Prefix lookup/11590.5.cpp

   1 /*
   2   Runtime error
   3  */
   4 #include <iostream>
   5 #include <cstdio>
   6 #include <cstring>
   7 #include <cassert>
   8 using namespace std;
   9
  10 #define D(x) cout << #x " is " << (x) << endl
  11
  12 typedef unsigned long long uint64;
  13
  14 const int BUFSIZE = 512;
  15 char buf[BUFSIZE];
  16
  17 struct node{
  18     string s;
  19     bool end;
  20     node * left;
  21     node * right;
  22     node(bool end) : end(end) {
  23         left = right = NULL;
  24         s = "";
  25     }
  26     node * getLeft(){
  27         if (left == NULL) left = new node(false);
  28         return left;
  29     }
  30     node * getRight(){
  31         if (right == NULL) right = new node(false);
  32         return right;
  33     }
  34 };
  35
  36 //return 2^e
  37 uint64 pow2(int e){
  38     if (e == 64) return 0;
  39     return uint64(1) << e;
  40 }
  41
  42 void clean(node * cur){
  43   if (cur == NULL) return;
  44   clean(cur->left);
  45   clean(cur->right);
  46   delete cur;
  47 }
  48
  49 int n, m;
  50 /*
  51 Returns how many strings were counted under the tree rooted at cur, including it.
  52 */
  53 uint64 alreadyCounted(node * cur){
  54     if (cur == NULL) return 0;
  55     uint64 left = alreadyCounted(cur->left);
  56     uint64 right = alreadyCounted(cur->right);
  57     uint64 ret = left + right;
  58     if (cur->end){
  59         //count strings matched to this one
  60         ret += pow2(m - cur->s.size()) - left - right;
  61     }
  62     return ret;
  63 }
  64
  65
  66 int main(){
  67     while (true){
  68         scanf("%d", &n);
  69         scanf("%d", &m);
  70         while (getchar() != '\n');
  71         if (n == 0 && m == 0) break;
  72         node * root = new node(true);
  73         for (int i=0; i<n; ++i){
  74             node * cur = root;
  75             fgets(buf, BUFSIZE, stdin);
  76             for (int j=0; ; ++j){
  77                 if (buf[j] == '*'){
  78                     cur->end = true;
  79                     break;
  80                 }
  81                 node * next;
  82                 if (buf[j] == '0'){
  83                     next = cur->getLeft();
  84                     next->s = cur->s + '0';
  85                 }else if (buf[j] == '1'){
  86                     next = cur->getRight();
  87                     next->s = cur->s + '1';
  88                 }else{
  89                     printf("Bad character %c at query %d, position %d\n", buf[j], i, j);
  90                     //assert(false);
  91                 }
  92                 cur = next;
  93             }
  94         }
  95         fgets(buf, BUFSIZE, stdin);
  96         int k;
  97         sscanf(buf, "%d", &k);
  98         for (int i=0; i<k; ++i){
  99             fgets(buf, BUFSIZE, stdin);
 100             buf[strlen(buf)-1] = 0;
 101
 102             node * cur = root;
 103             for  (int j=0; buf[j] != '*'; ++j){
 104                 if (buf[j] == '0'){
 105                     cur = cur->left;
 106                 }else if (buf[j] == '1'){
 107                     cur = cur->right;
 108                 }
 109             }
 110             uint64 ans = pow2(m - cur->s.size()) - alreadyCounted(cur->left) - alreadyCounted(cur->right);
 111             cout << ans << endl;
 112         }
 113         while (getchar() != '\n'); //empty line
 114         printf("\n");
 115         clean(root);
 116     }
 117     return 0;
 118 }